package com.salim.leetcode.$153;

public class FindMinimuminRotatedSortedArray {
    public int findMin(int[] nums) {
        int maxIndex = findMaxIndex(nums,0,nums.length-1);
        if(maxIndex+1==nums.length){
            return nums[0];
        }else{
            return nums[maxIndex+1];
        }
    }

    public int findMaxIndex(int[] nums,int left,int right){
        if(left+1==right){
            if(nums[left]>nums[right]){
                return left;
            }else{
                return right;
            }
        }
        if(left==right){
            return right;
        }

        int middle = left+(right-left)/2;
        if(nums[left]<nums[middle]){
            return findMaxIndex(nums,middle,right);
        }else{
            int leftMaxIndex = findMaxIndex(nums,left,middle);
            int rightMaxIndex;
            if(middle+1>=right){
                rightMaxIndex = right;
            }else{
                rightMaxIndex = findMaxIndex(nums,middle+1,right);
            }
            if(nums[leftMaxIndex]>nums[rightMaxIndex]){
                return leftMaxIndex;
            }else{
                return rightMaxIndex;
            }
        }
    }

    public static void main(String[] args){
        int[] array = new int[]{3,4,5,1,2};
        FindMinimuminRotatedSortedArray findMinimuminRotatedSortedArray = new FindMinimuminRotatedSortedArray();
        findMinimuminRotatedSortedArray.findMin(array);
    }
}
